Wireless devices communicate with each other either directly or via one or more base stations over a radio channel. The base station receives communications from one device and then forwards them, possibly over a network, to another device. The risk of disruption of any given wireless connection makes it difficult for a given base station to provide assurance to a communicating device that sufficient resources are available for the projected needs of the device. Moreover, wireless devices are mobile devices that are capable of moving out of range or losing signal strength due to other factors.
Many wireless devices use carrier sense multiple access with collision avoidance (“CSMA/CA”) technology. In accordance with CSMA each node monitors the carrier, e.g., a radio channel of interest, to detect if any other node is transmitting prior to attempting a transmission since CSMA/CA is based on the “listen before talk” paradigm. Carrier sense wireless network nodes can sense the carrier, i.e., transmissions over the common radio channel, from a transmitter in a larger range than the range at which receivers are willing to accept a packet from that same transmitter. In addition, the range for sensing the carrier is beyond the range within which the transmitter may cause interference. The detection of a transmitting node can be actual or based on a parameter declaring the time interval for which the transmitting node intends to transmit, i.e., virtual.
Every packet is sent by a node in contention-free periods to inform other nodes of the intended transmission. In response other nodes regulate their packet transmission attempts based only on their local perception of the state—idle or busy—of the radio channel. Such sensing results in the given node waiting for the radio channel to be idle for a prescribed period of time prior to attempting transmission. Detection of transmissions by another node in the radio channel results in a node that is currently waiting to transmit entering a “backoff” state. The duration of the backoff state, representing the time for which the common radio channel is required to be idle, is preferably set using a random number selected from a range, termed contention window in the IEEE 802.11 standard specifications, determined by the prior failed attempts to transmit. See, e.g., O' Hara, Bob and Al Peterick, “IEEE 802.11 handbook: A Designer's Companion,” IEEE Press New York (1999). However, CSMA/CA does not provide Quality of Service (“QoS”) guarantees.
QoS refers to a reservation of resources, such as bandwidth, time slices, relative priority, memory, ports and the like that are required for the execution of a desired task in a specified time period. Default QoS level, typically termed “best effort,” represents execution of a task if resources are available when needed, but not necessarily providing reservation of resources. In other words, “best effort” represents providing otherwise idle resources for carrying out the task. Higher levels of assurance provide better than “best effort” and can include several levels of relative priority as is discussed next.
Merely reserving resources such as bandwidth is not sufficient for efficiently providing QoS assurances. An added complication is the enhanced possibility of packet collisions due to two or more nodes attempting to transmit during overlapping time intervals over the common radio channel resulting in unsuccessful transmission. Packet collisions are unavoidable with wireless links connecting nodes because each node has a significantly delayed perception of other nodes' activity. Collisions also take place due to hidden nodes. For example, two transmitting nodes outside the sensing range of each other may interfere at a common receiver if they are within the sensing range of the common receiver.
Following a determination of an anticipated level of the resources required by a task, often by the task itself, it is possible to reliably request a reservation of the resources, which may be distributed, at future times. Non-exhaustive examples of tasks requiring differing levels of anticipated resource needs include transmitting a large file, providing voice links, audio-video links and real-time execution of an interactive gaming application.
New wireless applications, such as news updates, emergency services and the like may benefit from a reservation mechanism, i.e., availability of non-default QoS that ensures satisfactory functioning of real-time applications. However, due to the transient nature of wireless links, which may be a part of a larger communication path, it is difficult to reserve resources without a significant likelihood of under-utilization of the transmission medium.
Some suggestions for providing QoS over wireless links include the black-burst (“BB”) contention mechanism discussed in Sobrinho, J. L. and A. S. Krishnakumar “Quality-of-Service in Ad Hoc Carrier Sense Multiple Access Wireless Networks” in IEEE Journal on Selected Areas in Communications, Volume 1, No. 8, 1353–1368 (1999). In accordance with BB, nodes contend for access to the common radio channel with pulses of duration proportional to the time spent waiting for the common radio channel to become idle. Id. Furthermore, BB provides priority to real-time traffic.
BB recognizes three types of links between nodes. First, a communication link between two nodes reflects successful transmission and receipt of a packet from one node to the other node. Second, an interfering link between two nodes due to transmissions from one of the nodes colliding with any other transmission to the other node during the same time interval. Finally, a sensing link between two nodes reflecting that one of the nodes can sense if the other node is transmitting. Naturally, if two nodes have a communication link between them then they also have interfering and sensing links between them.
CSMA/CA, in accordance with the IEEE 802.11 standard, allows for a backoff mode for a node that is otherwise ready for transmit a packet. A node in the backoff mode chooses a random number s uniformly distributed between zero and min{32×2c−1, 1, 255}, where c is the number of collisions experienced by the node since its last successful transmission. The node, then, sets a timer that counts down only while the channel has been perceived idle for more than a threshold for transmitting on the common radio channel and (re)transmits the packet when the timer reaches zero. Furthermore, a node learns of the success or failure of its transmission following reception of a positive acknowledgment scheme. The recipient of a correctly received packet sends back an acknowledgment packet within a bounded interval of time. Id.
Contention between nodes, in accordance with BB allows resolution of collisions between nodes. Nodes contend for the common radio channel prior to the time when they would be allowed to transmit. Contending nodes transmit bursts of energy (hereinafter “burst transmission”) of duration proportional to the individual delay experienced by a node. Following a burst transmission a node monitors the common radio channel to determine if its burst was the longest. The successful node proceeds with its transmission while the other nodes wait to contend for the common radio channel to become idle again. The successful node also selects a future time for transmission of the next transmission. Thus, the various nodes transmit in staggered time intervals that are more likely to be collision free.
However, this scheme requires transmission of bursts of energy, an expensive scheme for devices with limited power resources. Using additional hardware and/or software to detect that such bursts are not packet transmissions is also required for implementing the BB proposal. Furthermore, the transient nature of wireless and other failure prone connections is likely to repeatedly invoke the burst mechanism to resynchronize real-time transmissions.
A further limitation of proposals for providing QoS, including BB discussed above and WHITECAP™ over transient links is the widely perceived need to extend existing standards such as IEEE 802.11. Both the BB and the WHITECAP™ proposals seek to extend existing standards. In other words, agreement has to be reached among the standards consortia members to accept a particular solution.
Furthermore, the proposed direction for standards is not efficiently addressed by the current proposals to provide QoS over wireless links. For instance the IEEE 802.1p proposal includes multiple priority levels for packet transmission—as many as eight priority levels have been proposed. Thus, QoS protocols need to accommodate several priority levels in addition to best-effort and real-time constraints in resolving collisions with the aim of honoring QoS guarantees.